
// 按每个区间开头大小升序排序
// 排序后，使用变量tmp保存当前区间，遍历所有区间，每次只会面对两种情况：
// 当前区间和tmp 相邻或者重叠， 可以合并成一个连续的大区间
// 当前区间与tmp不重叠， 说明tmp是的独立的区间，添加到结果中

var merge = function(intervals) {
    if (intervals.length === 0) return [];
    // 按每个区间的开头大小排序
    intervals.sort((a, b) => {
      return a[0] - b[0];
    });
    let res = [];
    let tmp = intervals[0];
    for (let interval of intervals) {
      // 有重叠，可以合并
      if (interval[0] <= tmp[1]) {
        tmp = [ tmp[0], Math.max(interval[1], tmp[1]) ];
      } else { // 无重叠， tmp是独立的区间，记录到结果中
        res.push([].concat(tmp));
        tmp = interval;
      }
    }
    res.push(tmp);// 最后的区间
  
    return res;
  };


//   vector<vector<int>> merge(vector<vector<int>>& intervals) {
//     sort(intervals.begin(), intervals.end());
//     vector<vector<int>> ans;
//     for (int i = 0; i < intervals.size();) {
//         int t = intervals[i][1];
//         int j = i + 1;
//         while (j < intervals.size() && intervals[j][0] <= t) {
//             t = max(t, intervals[j][1]);
//             j++;
//         }
//         ans.push_back({ intervals[i][0], t });
//         i = j;
//     }
//     return ans;
// }

// 作者：ikaruga
// 链接：https://leetcode.cn/problems/merge-intervals/solution/merge-intervals-by-ikaruga/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。